
import java.util.*;

/**
 *
 * @author Alex & Umit
 */

public class BinTree
{
    private TNode root;
    private int size;

    public BinTree()
    {
        root = null;
        size = 0;
    }

    /**
     * True if root == null
     * @return
     */
    public boolean isEmpty()
    {
        return root == null;
    }

    /**
     * @return
     */
    public int size()
    {
        return size;
    }

    /**
     * Calculates size from a certain position.
     * @return
     */
    public int size(Position p)
    {
        
         if(hasLeft(p) && hasRight(p))
            return 1 + size(leftChild(p)) + size(rightChild(p));

        else if(hasRight(p) && !hasLeft(p))
            return 1 + size(rightChild(p));

        else if(!hasRight(p) && hasLeft(p))
            return 1 + size(leftChild(p));
         
        else return 1;
    }

    /**
     * Adds a new root to the top of the tree.
     * @param o Object to add
     * @throws NonEmptyTreeException if there is a root
     */
    public void addRoot(Object o)
    {
        if (isEmpty())
        {
            root = new TNode(o, null, null, null);
            size++;
        }
        else
            throw new NonEmptyTreeException("attempting to add to !empty tree");
    }

    /**
     * Get the root of the tree.
     * @return root
     * @throws EmptyTreeException if the tree is empty
     */
    public Position root()
    {
        if (!isEmpty())
            return root;
        else
            throw new EmptyTreeException("attempting to return empty tree");
    }

    /**
     * Check to see if we are the root node.
     * @param p Node to check
     * @return
     */
    public boolean isRoot(Position p)
    {
        return toTNode(p) == root;
    }

    /**
     * Check to see if arg has a left child.
     * @param p Position to check
     * @return result
     */
    public boolean hasLeft(Position p)
    {
        return toTNode(p).left() != null;
    }

    /**
     * Check to see if arg has a right child.
     * @param p Position to check
     * @return result
     */
    public boolean hasRight(Position p)
    {
        return toTNode(p).right() != null;
    }

    /**
     * Attempt to insert an object as left child.
     * @param p Where to insert at
     * @param o Object to insert
     */
    public void insertLeft(Position p, Object o)
    {
        if (!hasLeft(p))
        {
            TNode tmp = toTNode(p);
            tmp.setLeft(new TNode(o, tmp, null, null));
            size++;
        }
        else
            throw new InvalidPositionException("Already have a left child!");
    }

    /**
     * Attempt to insert an object as right child.
     * @param p Where to insert at
     * @param o Object to insert
     */
    public void insertRight(Position p, Object o)
    {
        if (!hasRight(p))
        {
            TNode tmp = toTNode(p);
            tmp.setRight(new TNode(o, tmp, null, null));
            size++;
        }
        else
            throw new InvalidPositionException("Already have a right child!");
    }

    /**
     * Try to get left child
     * @param p Where we're getting the child from
     * @return result
     */
    public Position leftChild(Position p)
    {
        if (hasLeft(p))
            return toTNode(p).left();
        else
            throw new BoundaryViolationException("no left child");
    }

    /**
     * Try to get right child
     * @param p Where we're getting the child from
     * @return result
     */
    public Position rightChild(Position p)
    {
        if (hasRight(p))
            return toTNode(p).right();
        else
            throw new BoundaryViolationException("no right child");
    }

    /**
     *
     * @param p
     * @return
     */
    public boolean isLeft(Position p)
    {
        if (isRoot(p))
            return false;

        TNode tmp = toTNode(p);

        return tmp == tmp.parent().left();
    }

    /**
     *
     * @param p
     * @return
     */
    public boolean isRight(Position p)
    {
        if (isRoot(p))
            return false;

        TNode tmp = toTNode(p);

        return tmp == tmp.parent().right();
    }

    /**
     *
     * @param p
     * @return
     */
    public boolean hasParent(Position p)
    {
        return !isRoot(p);
    }

    /**
     *
     * @param p
     * @return
     */
    public Position parent(Position p)
    {
        if (hasParent(p))
            return toTNode(p).parent();
        else
            throw new BoundaryViolationException("no parent");
    }

    /**
     * Does p have a left or right child?
     * @param p
     * @return
     */
    public boolean isInternal(Position p)
    {
        return hasLeft(p) || hasRight(p);
    }

    /**
     * Does p not have children?
     * @param p
     * @return
     */
    public boolean isExternal(Position p)
    {
        return !isInternal(p);
    }


    /**
     *
     * @param p
     * @param o
     * @return
     */
    public Object replaceElement(Position p, Object o)
    {
        Object tmp = (Object)toTNode(p).element();

        toTNode(p).setElem(o);

        return tmp;
    }

    /**
     *
     * @param p
     * @param q
     */
    public void swapElement(Position p, Position q)
    {
        TNode first = toTNode(p);
        TNode second = toTNode(q);
        Object tmp = first.element();

        first.setElem(second.element());
        second.setElem(tmp);
    }

    /**
     *
     * @param p
     * @return
     */
    public int depth(Position p)
    {
        // return 0 if p is the root node else recursively calculate depth
        return isRoot(p) ? 0 : 1 + depth(parent(p));
    }
    
     /**
     *
     * @return
     */
    public Iterator positions()
    {
        ArrayList<Object> tmp = new ArrayList<Object>(size());
        
        inorderPositions(root(), tmp);
        
        return tmp.iterator();
    }

    /**
     *
     * @return
     */
    public Iterator elements()
    {
        ArrayList<Object> tmp = new ArrayList<Object>(size());

        inorderElements(root(), tmp);

        return tmp.iterator();
    }

    private void inorderPositions(Position p, ArrayList<Object> aList)
    {
        if (hasLeft(p))
            inorderPositions(leftChild(p), aList);

        aList.add(aList.size(), toTNode(p));

        if (hasRight(p))
            inorderPositions(rightChild(p), aList);
    }

    private void inorderElements(Position p, ArrayList<Object> aList)
    {
        if (hasLeft(p))
            inorderElements(leftChild(p), aList);

        aList.add(aList.size(), toTNode(p).element());

        if (hasRight(p))
            inorderElements(rightChild(p), aList);
    }

    @Override
    public String toString()
    {
        if (isEmpty())
            throw new EmptyTreeException("toString()");
        else
            return toString(root, 0);
    }

    /**
     *
     * @param p
     * @param indents
     * @return
     */
    public String toString(Position p, int indents)
    {
        String tab = "   ";
        String tabs = "";

        for (int i = 0; i < indents; i++)
            tabs += tab;

        TNode t = toTNode(p);
        String res = "";
        res = tabs + "<BinTree(" + t;

        if (hasLeft(t))
            res += "\n" + toString(t.left(), indents + 1);
        else
            res += "\n" + tabs + tab + "()";

        if (hasRight(t))
            res += "\n" + toString(t.right(), indents + 1);
        else
            res += "\n" + tabs + tab + "()";

        res += "\n" + tabs + ")>";

        return res;
    }

    protected TNode toTNode(Position p)
    {
        // helper cast function
        if(p == null) throw new NullPointerException();
        if (p instanceof TNode)
            return (TNode) p;
        else
            throw new AssertionError("casting error");
    }
}

